#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
const ll maxn = 2e3 + 1, maxm = 1e3 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;
int t, timer;
int n, m;
int dp[maxn], tin[maxn], used[maxn], color[maxn], colc[maxn], par[maxn];
vector<int> g[maxn], g2[maxn];
int foo[maxn], bar[maxn];
map<pair<int, int>, int> reb;
map<int, int> fix;
vector<int> ans;
void dfs(int v, int p){
used[v] = 1;
tin[v] = ++timer;
dp[v] = tin[v];
for (auto to : g[v]){
if (to != p){
if (used[to]){
dp[v] = min(dp[v], tin[to]);
}
else{
dfs(to, v);
dp[v] = min(dp[v], dp[to]);
if (dp[to] > tin[v]){
reb[mp(v, to)] = 1;
reb[mp(to, v)] = 1;
}
}
}
}
}
void dfs2(int v, int c){
used[v] = 1;
color[v] = c;
colc[c] += 1;
for (auto to : g2[v]){
if (used[to] == 0){
dfs2(to, c);
}
}
}
void dfs3(int v, int p, int root){
if ((int)ans.size() > 0){
return;
}
used[v] = 1;
for (auto to : g[v]){
if ((int)ans.size() > 0){
return;
}
if (color[to] != color[root] || fix[to] || to == p){
continue;
}
if (used[to] == 0){
par[to] = v;
dfs3(to, v, root);
}
else{
if (to == root){
while (v != to){
ans.pb(v);
v = par[v];
}
ans.pb(v);
return;
}
}
}
}
int main(){
cin >> t;
// cout << t << '\n';
while (t--){
cin >> n >> m;
for (int i = 1; i <= m; ++i){
cin >> foo[i] >> bar[i];
int u = foo[i], v = bar[i];
g[u].pb(v);
g[v].pb(u);
}
timer = 0;
for (int i = 1; i <= n; ++i){
g2[i].clear();
colc[i] = 0;
color[i] = 0;
used[i] = 0;
dp[i] = 0;
tin[i] = 0;
}
fix.clear();
ans.clear();
reb.clear();
//5 7
//3 5
//5 2
//2 4
//2 1
//4 3
//2 3
//1 4
for (int i = 1; i <= n; ++i){
if (used[i] == 0){
dfs(i, 0);
}
}
for (int i = 1; i <= m; ++i){
int u = foo[i], v = bar[i];
if (reb[mp(u, v)] == 0){
g2[u].pb(v);
g2[v].pb(u);
}
}
for (int i = 1; i <= n; ++i){
used[i] = 0;
}
int col = 0;
for (int i = 1; i <= n; ++i){
if (used[i] == 0){
dfs2(i, ++col);
}
}
for (int i = 1; i <= n; ++i){
used[i] = 0;
}
vector<pair<int, int>> answ;
for (int i = 1; i <= n; ++i){
if (colc[color[i]] > 1 && (int)g[i].size() >= 4){
for (int j = 0; j < 4 && (int)answ.size() == 0; ++j){
for (int k = j + 1; k < 4 && (int)answ.size() == 0; ++k){
for (int is = 1; is <= n; ++is){
used[is] = 0;
}
int u = g[i][j];
int v = g[i][k];
fix[u] = 1;
fix[v] = 1;
dfs3(i, -1, i);
if ((int)ans.size() > 0){
int nn = (int)ans.size();
for (int is = 0; is < nn; ++is){
answ.pb(mp(ans[is], ans[(is + 1) % nn]));
}
answ.pb(mp(i, u));
answ.pb(mp(i, v));
}
fix[u] = 0;
fix[v] = 0;
}
}
}
}
if ((int)answ.size() > 0){
cout << "YES\n";
cout << (int)answ.size() << '\n';
for (auto it : answ){
cout << it.f << " " << it.s << '\n';
}
}
else{
cout << "NO\n";
}
timer = 0;
for (int i = 1; i <= n; ++i){
g[i].clear();
g2[i].clear();
colc[i] = 0;
color[i] = 0;
used[i] = 0;
}
fix.clear();
ans.clear();
reb.clear();
}
}
/*
*/
Non empty subsets | 1630A - And Matching |
1630B - Range and Partition | 1630C - Paint the Middle |
1630D - Flipping Range | 1328A - Divisibility Problem |
339A - Helpful Maths | 4A - Watermelon |
476A - Dreamoon and Stairs | 1409A - Yet Another Two Integers Problem |
977A - Wrong Subtraction | 263A - Beautiful Matrix |
180C - Letter | 151A - Soft Drinking |
1352A - Sum of Round Numbers | 281A - Word Capitalization |
1646A - Square Counting | 266A - Stones on the Table |
61A - Ultra-Fast Mathematician | 148A - Insomnia cure |
1650A - Deletions of Two Adjacent Letters | 1512A - Spy Detected |
282A - Bit++ | 69A - Young Physicist |
1651A - Playoff | 734A - Anton and Danik |
1300B - Assigning to Classes | 1647A - Madoka and Math Dad |
710A - King Moves | 1131A - Sea Battle |